Computer networks are designed to allow various devices to communicate together. These devices include computers, servers, wireless devices, such as personal digital assistants (PDAs) and intermediate devices, such as switches and routers. These intermediate devices are used for a number of purposes. Switches may be included in a network if the distance between the two devices is greater than that allowed by the relevant network specification. Switches are also used to expand the size of the network, by allowing many additional paths of communications. Similarly, switches are used to create redundancy within the network. For example, switches may be included in a network to insure that there are at least two paths between each set of devices. In this way, the system is able to operate in the event of a failure or malfunction that affects one path, by routing traffic through the alternate path.
There are a number of different methods that these devices can use to communicate. The most common form of communication is that from a single source to a single destination, also known as unicast traffic. Typically, the source transmits a packet of information, with some means of identifying the destination. In more complex networks, that message may be received by an intermediate device, such as a switch, which lies in the path between the source and the destination. After receipt, this switch then retransmits the message along the path toward the destination. While the packet may pass through a number of intermediate destinations, there is only one true destination, which is the device that the packet is ultimately intended for.
A second type of communication is known as multicast communication. Multicast communication allows a single source to communicate with a number of different destination devices by sending a single packet. There are various instances where multicast communication can be employed. For example, a server may be transmitting a multimedia presentation, such as a video training program, which is destined for a number of remote users. Rather than transmitting the video stream separately to each remote user, the network can employ a multicast communication. In this way, the server transmits a single video stream, with multiple destination addresses so that the presentation reaches all of the intended recipients. Other applications could include desktop video conferencing, corporation broadcasts, and television broadcasts. This approach can be very effective in reducing network traffic, in environments, such as those listed above, where one device is sending the same information to multiple devices. Additionally, multicast traffic is also used in network configuration, such as to inform all switching elements within the network to update their routing tables.
Many networks include devices known as switches, which accept packets from a number of ports and forward those packets toward their final destination. In the case of unicast packets, the switch receives the packet via one of its input ports, determines the required output port and places the packet on the corresponding output queue. If the requested output port is blocked or congested, then the packet is held in the queue until it can be transmitted. Once the packet has been transmitted, it can be discarded by the switch.
As previously stated, multicast traffic can reduce the volume of network traffic in certain environments. However, the nature of multicast packets necessitates a more complex architecture in the switch. Unlike unicast packets, which are destined for a single output port, a multicast packet is typically destined for several output ports. Each of these output ports may have different operating characteristics, such as different queue depths, and different amount of congestion. Therefore, a multicast packet that is destined for two different output ports may be transmitted immediately via one output port, but still be pending transmission via a second output port. Because of this difference in the behavior of multicast packets, they require a specialized architecture.
The simplest way of handling multicast packets is to store all multicast packets in a separate multicast queue as they arrive as shown in FIG. 1. When a packet reaches the head of the queue, the switch determines the various destination output ports. The packet then remains at the head of the queue until it has been successfully transmitted via all selected output ports. This method has a serious limitation in that congestion at one output port causes all other multicast packets in the queue to be blocked. For example, assume that the multicast packet at the head of the queue is intended for ports 0 and 1, and that the next several packets are intended for ports 2 and 3. Congestion at output port 0 will force the first packet to remain at the head of the queue until the congestion is resolved. Note that the other packets in the queue, which were not intended for the congested port 0, are forced to wait until output port 0 can send the first multicast packet. This condition, referred to as head of line blocking, can seriously impact network performance.
Alternatively, this scheme can be implemented such that the queue stores only a pointer to the actual multicast packet. This embodiment reduces the amount of storage required and also reduces the number of times and locations to which the multicast packet must be written within the device. In essence, each entry in the queue is an address, where that address corresponds to the actual location of the multicast packet within the chip.
Typically, rather than identify each output port in a multicast packet, multicast packets contain a data field that identifies this set of ports. This field is commonly known as a multicast group identifier (MGID). Therefore, in the example above, the first packet may be intended for MGID 0, which identifies ports 0 and 1 as the intended output ports. Similarly, the remaining packets may be intended for a different multicast group.
Therefore, it is possible to relieve the head of line blocking issue if, instead of a single queue associated with multicast packets, a set of queues is created as shown in FIG. 2. Each queue in this set of queues is associated with a single multicast group identifier. As with FIG. 1, these queues can be used to hold the actual packets or simply pointers to the packets.
While this embodiment resolves the head of line blocking issue raised with respect to the single multicast queue, it has some serious drawbacks. First, there can be a large number of potential multicast groups. This requires an equal number of queues, since there is a corresponding queue for each MGID. During initialization, the switch will typically communicate to each of its neighboring switches a number of multicast credits, which is the number of multicast packets which it is guaranteed to be able to store.
If there are N input ports, and the switch has communicated that it has M multicast credits, then the number of multicast packets that the switch must be able to store is given as N×M. However, since these credits are granted independent of the individual multicast group, it is not possible to predict the distribution of multicast groups that are received. In other words, it is possible that all of the incoming packets may belong to a single multicast group. Thus, in order to guarantee that the switch is able to store and process all of the incoming multicast packets, each queue must be able to store N×M multicast packets (or pointers). Depending on the number of multicast groups that are supported, this may require a prohibitively large amount of storage to be allocated to this function.
In addition to the amount of storage required, this implementation leads to large deviations in latency. For example, suppose that MGID0 denotes multicast packets destined for output ports 0 and 1, while MGID1 denotes multicast packets destined for output ports 1 and 2. Further assume that multicast packets arrive in the following sequence:    P1(MGID0),P2(MGID0),P3(MGID1),P4(MGID1),P5(MGID0),P6(MGID1)
If output port 0 is congested, then packets P1, P2 and P5 will remain in their respective queue. During this time, packets P3, P4 and P6 are all transmitted to output ports 1 and 2, even though they all arrived after P1 and P2. This creates a large deviation in the amount of latency that each multicast packet experiences.
Furthermore, packets P2 and P5 could have been transmitted via output port 1, even while output port 0 was congested. These multicast packets could then be transmitted via output port 0 at a later time when the congestion on that port was alleviated. Thus, packets within a single MGID queue will still experience head of line blocking with respect to the non-congested output ports associated with that multicast group.
As described earlier, the aforementioned embodiment is improved by using queues of pointers rather than queues of packets. In this embodiment, all multicast packets are stored in a common storage element. For example, if a multicast packet for MGID 0 arrived, it would be placed in the common storage area. Its address in that common storage area would then be stored in the queue associated with that MGID. This embodiment requires less storage than the previous embodiment, since the storage area only needs to accommodate N×M packets, rather than N×M×(the number of groups). However, some networks allow for hundreds of multicast groups. Even though this embodiment only requires a queue of pointers per MGID, the storage requirements to support large numbers of multicast groups can still be prohibitive, since each queue must be capable of storing N×M entries. In addition, the drawbacks associated with latency and head of line blocking described with respect to FIG. 2 are still present in this embodiment.
An architecture and method for efficiently processing and transmitting multicast packets with minimal storage requirements and improved performance is needed.